package array.hard;

/**
 * 分割数组的最大值
 * 示例 1：
 *
 * 输入：nums = [7,2,5,10,8], m = 2
 * 输出：18
 * 解释：
 *
 * 一共有四种方法将 nums 分割为 2 个子数组。 其中最好的方式是将其分为 [7,2,5] 和 [10,8] 。
 * 因为此时这两个子数组各自的和的最大值为18，在所有情况中最小。
 * 示例 2:
 * 输入：nums = [1,2,3,4,5], m = 2
 * 输出：9
 * 示例 3：
 *
 * 输入：nums = [1,4,4], m = 3
 * 输出：4
 * 链接：https://leetcode-cn.com/problems/split-array-largest-sum
 */
public class SplitArrayLargestSum_410 {

    public int splitArray(int[] nums, int m) {
        int sum = 0;
        int max = 0;
        for (int num : nums) {
            sum += num;
            max = Math.max(max, num);
        }

        int l = max, r = sum;
        while (l < r) {
            int mid = (l + r) >> 1;
            if (check(nums, mid, m)) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }

    /**
     *
     * @param nums
     * @param t 区间最大
     * @param m 是否超过分割数
     * @return
     */
    public boolean check(int[] nums, int t, int m) {
        int sum = nums[0];
        int n = 1;
        for (int i = 1; i < nums.length; n++) {
            while(i < nums.length && sum + nums[i] <= t) {
                sum += nums[i];
                i++;
            }
            sum = 0;
        }
        return n - 1 <= m;
    }

}
